{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import logging\n",
    "from gen_inst import TSPInstance, load_dataset\n",
    "from gls import guided_local_search\n",
    "import time\n",
    "import elkai\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "perturbation_moves_map = {\n",
    "    20: 5,\n",
    "    50: 30,\n",
    "    100: 40,\n",
    "    200: 40,\n",
    "}\n",
    "iter_limit_map = {\n",
    "    20: 73,\n",
    "    50: 175,\n",
    "    100: 1800,\n",
    "    200: 800,\n",
    "}\n",
    "SCALE = 1000000\n",
    "test_sizes = list(iter_limit_map.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heuristics_reevo(distance_matrix: np.ndarray) -> np.ndarray:\n",
    "    # Calculate the average distance for each node\n",
    "    average_distance = np.mean(distance_matrix, axis=1)\n",
    "\n",
    "    # Calculate the distance ranking for each node\n",
    "    distance_ranking = np.argsort(distance_matrix, axis=1)\n",
    "    \n",
    "    # Calculate the mean of the closest distances for each node\n",
    "    closest_mean_distance = np.mean(distance_matrix[np.arange(distance_matrix.shape[0])[:, None], distance_ranking[:, 1:5]], axis=1)\n",
    "\n",
    "    # Initialize the indicator matrix and calculate ratio of distance to average distance\n",
    "    indicators = distance_matrix / average_distance[:, np.newaxis]\n",
    "\n",
    "    # Set diagonal elements to np.inf\n",
    "    np.fill_diagonal(indicators, np.inf)\n",
    "\n",
    "    # Adjust the indicator matrix using the statistical measure\n",
    "    indicators += closest_mean_distance[:, np.newaxis] / np.sum(distance_matrix, axis=1)[:, np.newaxis]\n",
    "\n",
    "    return indicators\n",
    "\n",
    "def vanilla_ktsp(distance_matrix: np.ndarray) -> np.ndarray:\n",
    "    return distance_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_cost(inst: TSPInstance, path: np.ndarray):\n",
    "    return inst.distmat[path, np.roll(path, 1)].sum().item()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "tsp20: 100%|██████████| 64/64 [00:00<00:00, 297.51it/s]\n",
      "tsp50: 100%|██████████| 64/64 [00:02<00:00, 21.66it/s]\n",
      "tsp100: 100%|██████████| 64/64 [00:22<00:00,  2.79it/s]\n",
      "tsp200: 100%|██████████| 64/64 [02:13<00:00,  2.08s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{20: 3.8362853943492015, 50: 5.68457994395107, 100: 7.778580370400294, 200: 10.71194600194464}\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "# Precompute the optimal solutions\n",
    "optimal_objs_dict = {}\n",
    "for problem_size in test_sizes:\n",
    "    dataset_path = f\"dataset/test{problem_size}_dataset.npy\"\n",
    "    dataset = load_dataset(dataset_path)\n",
    "    n_instances = dataset[0].n\n",
    "    logging.info(f\"[*] Evaluating {dataset_path} with LKH\")\n",
    "\n",
    "    optimal_objs = []\n",
    "    for i, instance in enumerate(tqdm(dataset, desc=f\"tsp{problem_size}\")):\n",
    "        elkai_dist = elkai.DistanceMatrix(((instance.distmat * SCALE).astype(int)).tolist()) \n",
    "        optimal_route = elkai_dist.solve_tsp() # e.g. [0, 2, 1, 0]; with proven optimal solutions up to N=315 (https://github.com/fikisipi/elkai)\n",
    "        optimal_obj = calculate_cost(instance, np.array(optimal_route[:-1]))\n",
    "        optimal_objs.append(optimal_obj)\n",
    "        \n",
    "    mean_optimal_obj = np.mean(optimal_objs)\n",
    "\n",
    "    optimal_objs_dict[problem_size] = mean_optimal_obj\n",
    "    \n",
    "print(optimal_objs_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "optimal_objs_dict = {20: 3.8362853943492015, 50: 5.68457994395107, 100: 7.778580370400294, 200: 10.71194600194464}\n",
    "\n",
    "def solve(inst: TSPInstance, heuristics):\n",
    "    start_time = time.time()\n",
    "    heu = heuristics(inst.distmat.copy())\n",
    "    result = guided_local_search(inst.distmat, heu, perturbation_moves_map[inst.n], iter_limit_map[inst.n])\n",
    "    duration = time.time() - start_time\n",
    "    return calculate_cost(inst, result), duration\n",
    "\n",
    "def evaluate(function):\n",
    "    print(\"[*] Function:\", function.__name__, \"\\n\")\n",
    "    for problem_size in iter_limit_map.keys():\n",
    "        dataset_path = f\"dataset/test{problem_size}_dataset.npy\"\n",
    "        dataset = load_dataset(dataset_path)\n",
    "        logging.info(f\"[*] Evaluating {dataset_path}\")\n",
    "\n",
    "        objs = []\n",
    "        durations = []\n",
    "        for instance in tqdm(dataset):\n",
    "            obj, duration = solve(instance, function)\n",
    "            objs.append(obj)\n",
    "            durations.append(duration)\n",
    "\n",
    "        mean_obj = np.mean(objs).item()\n",
    "        mean_optimal_obj = optimal_objs_dict[problem_size]\n",
    "        gap = mean_obj / mean_optimal_obj - 1\n",
    "        print(f\"[*] Average for {problem_size}: {mean_obj:.6f} ({mean_optimal_obj:.6f})\")\n",
    "        print(f\"[*] Optimality gap: {gap*100:.6f}%\")\n",
    "        print(f\"[*] Total/Average duration: {sum(durations):.6f}s {sum(durations)/len(durations):.6f}s\")\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Function: heuristics_reevo \n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:00<00:00, 939.19it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Average for 20: 3.836285 (3.836285)\n",
      "[*] Optimality gap: 0.000000%\n",
      "[*] Total/Average duration: 0.066535s 0.001040s\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:02<00:00, 31.33it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Average for 50: 5.684580 (5.684580)\n",
      "[*] Optimality gap: 0.000000%\n",
      "[*] Total/Average duration: 2.030284s 0.031723s\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [01:38<00:00,  1.54s/it]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Average for 100: 7.778580 (7.778580)\n",
      "[*] Optimality gap: 0.000000%\n",
      "[*] Total/Average duration: 98.809937s 1.543905s\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [02:41<00:00,  2.53s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Average for 200: 10.735125 (10.711946)\n",
      "[*] Optimality gap: 0.216382%\n",
      "[*] Total/Average duration: 161.792599s 2.528009s\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "evaluate(heuristics_reevo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Function: vanilla_ktsp \n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:00<00:00, 899.50it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Average for 20: 3.836448 (3.836285)\n",
      "[*] Optimality gap: 0.004242%\n",
      "[*] Total/Average duration: 0.069592s 0.001087s\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "  0%|          | 0/64 [00:00<?, ?it/s]"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [00:02<00:00, 31.38it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Average for 50: 5.685538 (5.684580)\n",
      "[*] Optimality gap: 0.016862%\n",
      "[*] Total/Average duration: 2.026035s 0.031657s\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [01:39<00:00,  1.55s/it]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Average for 100: 7.778761 (7.778580)\n",
      "[*] Optimality gap: 0.002327%\n",
      "[*] Total/Average duration: 99.047483s 1.547617s\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 64/64 [02:39<00:00,  2.50s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*] Average for 200: 10.742373 (10.711946)\n",
      "[*] Optimality gap: 0.284046%\n",
      "[*] Total/Average duration: 159.731591s 2.495806s\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "evaluate(vanilla_ktsp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
